home *** CD-ROM | disk | FTP | other *** search
/ PD ROM 1 / PD ROM Volume I - Macintosh Software from BMUG (1988).iso / Stacks / Updates⁄New / TEXAS for BMUG / C progs / qndxr.2 ƒ / qndxr.2.c < prev    next >
Encoding:
Text File  |  1987-11-03  |  6.6 KB  |  162 lines  |  [TEXT/KAHL]
  1. /*    revised main indexer program 'qndxr.c' by ^z -- 870820-...
  2.  *
  3.  * revised 870930-1002 to give the user more options and control of how
  4.  * delimiters are defined and handled.  Now can choose:
  5.  *    - the default:  any non-alphanumeric characters are delimiters (my
  6.  *        original approach, and perhaps the simplest to understand and use);
  7.  *    - option "-e":  keep punctuation characters ONLY when they are embedded
  8.  *        in between non-delimiter characters, otherwise turn them into
  9.  *        delimiters (approach invented by Bill Hole of MicroDynamics Ltd.;
  10.  *        very nice for displaying 'words' such as don't, non-ASCII, 3.14159,
  11.  *        87/10/02, etc. without splitting them up and requiring proximity
  12.  *        searching);
  13.  *    - option "-a":  keep ALL punctuation characters, whether embedded in
  14.  *        words or not (best for indexing FORTH programs and such, but does
  15.  *        make spurious 'distinct' words at ends of sentences, etc.);
  16.  *    - option "-s":  keep all special (non-ASCII) characters (with values
  17.  *        in the range 128-255; in the Apple character set, these are the
  18.  *        symbols that carry umlauts, tilde, accents, etc., making this
  19.  *        option the best for foreign-language and symbol-heavy files);
  20.  *        default is to remove the special characters.
  21.  *
  22.  *    Note that option "-s" can be combined with any of the other options;
  23.  *    options "-e" and "-a" are mutually exclusive.  (Actually, "-a" in my
  24.  *    implementation overrides "-e".)  The "-e" option does require
  25.  *    peeking ahead one character before deciding on the fate of
  26.  *    a punctuation symbol, but that isn't too hard to arrange....
  27.  *
  28.  *    ---------------------------------------------------------------
  29.  *
  30.  * Synopsis of the qndxr.c program's approach to sorting an index:
  31.  *    - load a chunk of the input file into memory; during the loading,
  32.  *        filter the characters appropriately, turning lower-case
  33.  *        into capitals, changing delimiters into \0's, and noting down
  34.  *        the locations of the beginnings of keys (words) in a ptr array;
  35.  *    - do a quicksort on the ptr array, using the keys in the buffer
  36.  *        to sort on;
  37.  *    - write the resulting sorted list of pointers along with their keys
  38.  *        to disk as files, named x0k0 and x0p0, in the *.k and *.p formats
  39.  *        used in ndxr.15;
  40.  *    - repeat the above steps with another chunk of the input file, and
  41.  *        name the resulting files x0k1 and x0p1; repeat, etc., until the
  42.  *        input file is all sorted into chunks;
  43.  *    - begin to merge the sorted files in an N-way merge ... for the
  44.  *        specific case of N=2, for example, merge x0k0/x0p0 and
  45.  *        x0k1/x0p1 into x1k0/x1p0; merge x0k2/x0p2 and x0k3/x0p3 into
  46.  *        x1k1/x1p1; etc., deleting the 0th-generation files as they are
  47.  *        merged;
  48.  *    - merge x1k0/x1p0 and x1k1/x1p1 into x2k0/x2p0, etc., and continue
  49.  *        merging subsequent generations until everything has become a
  50.  *        single pair of index files, xnk0/xnp0, which is then renamed
  51.  *        to be the original document name with '.k' and '.p' endings.
  52.  *
  53.  *    ---------------------------------------------------------------
  54.  *
  55.  * Comparison with the older radix sort approach:
  56.  *    The new quicksort/mergesort method gains a bit in speed (since so
  57.  *    much of the work is done in memory rather than streaming from disk
  58.  *    back and forth) and also saves on disk space requirements (since
  59.  *    the k and p files are significantly compressed relative to the raw
  60.  *    index files formerly used during index sorting).  The old radix sort
  61.  *    tended to only achieve about 2 MB/hour indexing on my Mac Plus setup,
  62.  *    and it required 5-6 times the size of the original file in free
  63.  *    disk space during indexing.  This new approach achieves >4 MB/hour
  64.  *    in tests on the same Mac Plus, and only requires about 1.9 times
  65.  * the original file size in free space!
  66.  *
  67.  *    The new approach also allows for greater key length -- try recompiling
  68.  *    with KEY_LENGTH of 28, for instance -- without such severe disk space
  69.  *    penalties as the old radix sort would have incurred, and without severe
  70.  *    time penalties.  (Duplicate words in the chunks are only stored once
  71.  *    in the key file, though each must have an entry in the pointer file.)
  72.  *
  73.  *    The only obvious disadvantage of the quicksort/mergesort approach is
  74.  *    that it is an O(NlogN) procedure rather than O(N), and thus gets slower
  75.  *    when files get very large.  (Radix sorting is strictly linear in N,
  76.  *    in theory anyway.)
  77.  *
  78.  *    ---------------------------------------------------------------
  79.  *
  80.  *    For further details, contact the author:
  81.  *     Mark Zimmermann             science (at) NEMS.ARPA
  82.  *     9511 Gwyndale Dr.           [75066,2044] on CompuServe
  83.  *     Silver Spring, MD  20910
  84.  *     301-565-2166
  85.  *    ---------------------------------------------------------------
  86.  */
  87.  
  88. #include <stdio.h>
  89. #include <unix.h>
  90. #include <storage.h>
  91. #include <strings.h>
  92. #include <ctype.h>
  93. #include <proto.h>
  94. #include "qndxr.2.h"
  95.  
  96. /* define a global variable to hold the chosen size of a fundamental
  97.  * quantum of buffer space ... experiments with dynamically choosing
  98.  * it at runtime seem to cause occasional problems on the Macintosh,
  99.  * and have other risks with virtual memory systems, so default to
  100.  * DEFAULT_MEMSIZ total buffer space but let the user override with
  101.  * a command-line choice to suit ... see function set_zbufsiz() for
  102.  * further discussion....
  103.  */
  104. long zbufsiz;
  105.  
  106. /* define a global variable to tell whether or not all punctuation chars
  107.  * are kept...
  108.  */
  109. int keep_all_punct = FALSE;
  110.  
  111. /* define a global variable to tell whether or not only embedded punctuation
  112.  * characters are preserved...
  113.  */
  114. int keep_embedded_punct = FALSE;
  115.  
  116. /* define a global variable to tell whether or not to keep special,
  117.  * non-ASCII characters...
  118.  */
  119. int keep_special_chars = FALSE;
  120.  
  121. /* define a global variable to hold the (FILE *) for the document file
  122.  */
  123. FILE *doc_file;
  124.  
  125. /* main program to do the work ... 
  126.  */
  127.  
  128. void _main(argc, argv)
  129.   int argc;
  130.   char *argv[];
  131.   {
  132.       unsigned long start_time, end_time, time();
  133.     long set_params(), file_size();
  134.     char *ctime();
  135.  
  136.     time (&start_time);
  137.     printf ("Starting work:  %s\n", ctime (&start_time));
  138.     
  139.     printf ("\nOpening document file \"%s\"...\n", argv[1]);
  140.     doc_file = open_docfile (argc, argv);
  141.  
  142.     zbufsiz = set_params (argc, argv);
  143.     printf ("Using buffers of size %ld each...\n", zbufsiz);
  144.  
  145.     printf ("Beginning to build index...\n");
  146.     while (build_indices ());
  147.  
  148.     printf ("Beginning to merge index subfiles...\n");    
  149.     while (merge_indices (argv[1]));
  150.  
  151.       time (&end_time);
  152.       printf ("\nEnding work:  %s\n", ctime (&end_time));
  153.       printf ("Elapsed time  = %ld seconds.\n", end_time - start_time);
  154.       printf ("Indexing rate = %.2f megabytes/hour.\n", file_size (doc_file) *
  155.                   0.003600 / ( end_time - start_time ));
  156.       printf ("Input database file \"%s\" was %ld bytes long.\n", argv[1],
  157.                   file_size (doc_file));
  158.  
  159.       fclose (doc_file);
  160.   }
  161.  
  162.